//递归方法：
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
         // 首先是递归的出口
        if(head == nullptr||head->next == nullptr)
        {
            return head;
        }// 如果只有一个节点了/没有节点了直接返回即可
        // 然后我们要相信re这个函数能够帮助我们完成head后面所有节点的逆置，并且最后会返回新的头节点
        ListNode* newhead = reverseList(head->next);
        //然后我们逆置我们当前的这个节点即可
        head->next->next = head;
        head->next = nullptr;// 让这最后一个节点指向nullptr
        return newhead;
    }
};
//迭代方法：
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        ListNode* cur = head;
        ListNode* tail = nullptr;
        ListNode* newhead;
        while(cur!=nullptr)
        {
            ListNode* tmp = cur->next;
            if(tmp == nullptr)
            {
                newhead = cur;
            }
            cur->next = tail;
            tail = cur;
            cur = tmp;
        }
        return newhead;
         
    }
};